
'''
给定一个包含整数的数组，求这个数组中所有**连续元素的子数组**的**最大和**。

[3, -2, 4]

[3] -> 3
[-2] -> -2
[4] -> 4
[3, -2] -> 1
[-2, 4] -> 2
[3, -2, 4] -> 5
'''

'''
最大子数列和问题
3 5 -9 1

  3 5 -9 1 3 -2 3 4 7   2  -9 6   3   1   -5  4
[ 3 8 -1 1 4

1 + -1
1

                                              ]
[ 3 8 -1 1 4 2  5 9 16  18 9  15  18  19  14  18] 
'''
def kadane(arr):
    curr_value = arr[0]
    max_value = arr[0] # 最大相邻元素和

    for i in range(1, len(arr)):
        # 不断的计算以 arr[i] 为最后一个元素的子数组的和
        n = arr[i]
        curr_value = max(n, curr_value + n)
        max_value = max(max_value, curr_value)
    
    return max_value
